\input basic
\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\ctrline{\bf CS154 PROBLEM SET 6, SOLUTIONS}

5.1

(a) You will have one state in which you read characters and push them
onto the stack.  From this you make an epsilon transition to a second
state in which you read characters and compare them to the top of the stack.
If they are the same, then pop the stack; otherwise jam.  Accept by empty stack.

(b) When in the start state push a $\#$ onto the stack and go to a second state.
In this state when you read a left parenthesis, push it.  When you read
a right parenthesis check the top of stack to see if it is a left parenthesis.
If it is, then pop the stack.  Otherwise jam.  Whenever there is a $\#$ on
the top of the stack, allow an epsilon transition to an accepting state, which
will have no transitions out of it.  Accept by accepting state.

(b) When in the start state push a $\#$ onto the stack and go to a second state.
In this state, when you read an $a$, see what's on the top of the stack.  If
there is an $a$ on the top of the stack, pop it.  If the top of stack is
now a $b$, then pop it, too; otherwise, push the two $a$'s back onto the
stack.  When you read a $b$, see what's on the top of the stack.  If it is
a $b$ then push the $b$.  If it is an $a$, then pop the $a$.  If the new
top of stack is an $a$, then pop it, too; otherwise push the $b$ and then
push the $a$.  Allow an epsilon transition to an accepting state when there
is a $\#$ on top of the stack.  Accept by accepting state.

Comment:  The stack of this PDA will always look like $a*+b*+b*a$.

5.2

When in the start state, push an $S$ on the top of the stack.
When you read an $a$, pop the stack.  If the symbol popped off is an
$S$, then push $AA$.  If the symbol popped off is an $A$, then push an $S$,
or else do nothing.
When you read a $b$, pop the stack.  If the symbol popped off is an $A$,
then push an $S$; otherwise, jam.  Accept by empty stack.

5.8

Suppose the contrary, {\sl\ i.e.}, some DPDA accepts both $x$ and some proper
prefix of $x$ by empty stack.  But this is impossible, because the machine
would have halted after reading the prefix and before it finished reading
$x$.  Hence the DPDA could not accept $x$.

This is not true for NPDA's.
A non-deterministic PDA can accept any CFL by empty stack, in particular
the language $a+aa$, which doesn't have the prefix property.

\vfill\eject

5.9

If $L$ is $N(M)$ for some machine $M$, then I have just shown that $L$
has the prefix property.  Furthermore the construction used for showing
the equivalence of NPDA's that accept by empty stack and NPDA's that
accept by accepting state will build a DPDA, $M↑{\prime}$, such that
$L$ is $L(M↑{\prime})$.

Now I must show the converse of this.  Suppose that $L$ is $L(M↑{\prime})$
for some DPDA, $M↑{\prime}$, and that $L$ has the prefix property.  Construct a
machine from $M↑{\prime}$ that has the same transitions except that when it
enters an accepting state of $M↑{\prime}$, it empties its stack.  This
DPDA accepts $L$ by final state.  Notice that this construction fails
if $L$ does not have the prefix property.

\vfill\eject\end